package com.shuang.tree31;

import java.util.ArrayList;
import java.util.List;

public class PathSum {

    //递归 前序  搜索整个树且不需要处理返回值 所以递归不需要返回值
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {

        //用于封装结果
        List<List<Integer>> result = new ArrayList<>();

        if (root == null){
            return result;
        }

        //用于记录路径每个结点的值
        List<Integer> path = new ArrayList<>();

        //定义递归函数 封装结果
        preOrderDfs(root, targetSum, path, result);

        return result;
    }

    public void preOrderDfs(TreeNode root, int targetSum, List<Integer> path, List<List<Integer>> result){

        //中 路径记录
        path.add(root.val);

        //到达叶子节点
        if (root.left == null && root.right == null){
            if (targetSum - root.val == 0){
                //说明此路径可以封装到结果中
                //new ArrayList<>(path)是创建了新的实例 为了保留当前路径的状态，避免后续递归对 path 的修改影响已存储的结果。
                result.add(new ArrayList<>(path));
            }
            //到达叶子节点且目标值对不上 直接返回
            return;
        }

        //左
        if (root.left != null){
            //左 继续找
            preOrderDfs(root.left, targetSum - root.val, path, result);
            path.remove(path.size() - 1);  //回溯
        }

        //右
        if (root.right != null){
            //右 继续找
            preOrderDfs(root.right, targetSum - root.val, path, result);
            path.remove(path.size() - 1);  //回溯
        }
    }
}
